An application layer network multicast may use a tree-based topology. Several multicast trees may be wrapped around a ring-like network. For an application layer multicast each node in the network sends message packets from a publisher to one or more nodes downstream. The downstream nodes are referred to herein as children. By using a tree-based topology, the publisher doesn't need to send the message packets directly to all the recipients. When the message packets transmit streaming data, such as audio or video frames, a buffer at each node holds the frames of content before they are displayed on a screen as images or played through a speaker as sounds. Networks are generally less than perfectly reliable and some packets are typically lost in transmission between a node and its child or children. The lost packets create gaps in the feed of streaming media data. These gaps can result in abnormalities in the presentation of streaming media such as lost video frames, sound dropouts and the like.
Unfortunately, there can be unacceptable levels of packet loss in a network multicast of streaming data. This is due to the fact that errors (e.g., missing packets) may be generated at each level of nodes in the network. The errors, therefore, tend to accumulate as they propagate further along the tree. For example, consider a simple multicast tree where a publisher distributes messages to two first-level child nodes. Each of the two first-level child nodes, in turn each forwards the messages from the publisher to two second-level child nodes. Each of the second level child nodes forwards the messages from the first-level nodes to two third-level nodes and each third-level node passes these messages on to two fourth-level nodes. In this example there are thirty-one nodes in the tree, the publisher, two at the first level, four at the second level, eight at the third level and sixteen at the fourth level. If errors occur at each level at a certain rate, the error rate received from the level above is passed on to the level below. For example if errors occur at each level at a rate of 2%, those nodes at the first level receive errors at the 2% rate from the level above and additional errors occur at the first level a 2% rate. The first level nodes pass both (i.e., a 4% rate) to the second level. Similarly, the third level receives errors at a 6% rate and the fourth level receives an 8% rate. Thus, over half the nodes in the tree experience an 8% error rate.
Networks often use some form of forward error correction to fill in these gaps for static, i.e., non-streaming data. Forward error correction generally involves sending more information than is needed to fill the gaps. The forward error correction information is typically in the form of check packets. A downstream node receiving the check packets can generally lose any part of a file but still be able to reconstruct the whole file if enough check packets are received. The check packets are based on combinations of random message packets that have been logically combined through an operation such as a bit-wise Exclusive OR or XOR operation. Each bit in a check packet is the result of the XOR of one or more message packets. By way of example, in a bit-wise XOR operation between two digital messages bits in corresponding positions in the two messages are compared to each other. The resulting bit for the XOR of each pair of corresponding bits is a “0” if the two bits are the same and a “1” if the two bits are different. Table I shows a truth table for a bitwise XOR function for a pair of one bit messages A and B, each of which can take on the possible values of “1” or “0”.
TABLE IABA XOR B101011000110
For messages having more than one bit, the operation is performed on pairs of corresponding bits from each message. For example, Table II illustrates the XOR of the four bit message A=1 0 0 1 with the four-bit message B=0 1 1 1 to produce the four-bit check packet C.
TABLE IIA =1 0 0 1B =0 1 1 1A XOR B = C =1 1 1 0
It is a property of the XOR operation that if A XOR B=C, B=C XOR A and A=C XOR B. Furthermore. Where N−1 message packets are XOR'ed together to produce a check packet, e.g., A1 XOR A2 XOR . . . XOR AN-1 XOR AN=C, one can generally determine any one unknown message packet through a XOR of the other N−1 message packets and the check packet.
Since packets are dropped at random it is likely that two or more message packets may be lost for any given set of message packets. Forward error correction protocols typically generate a number of check packets to be sent from a node to its children. Generally, if there are N message packets in a static message, the nodes at each level forward (1+ε)N check packets to the next level, where ε is less than one. Fortunately, it is generally possible to generate an arbitrarily large number of check packets from randomly selected message packets.
Usually, the number of message packets selected for the purpose of generating the check packets is based on probability. Furthermore, the degree of the XOR operation used the nodes generate the check packets is chosen based on probability. As used herein the degree of a XOR operation refers to the number of elements (e.g., message packets) that are XOR'ed together.
Examples of such techniques are described e.g., in U.S. Pat. No. 6,307,487, which is incorporated herein by reference. Unfortunately, forward error correction of this type has not been applied to streaming media multicasts. The above problems are further compounded for streaming media since new message packets are being generated in a continuous stream. Thus, at any given instant in time, the nodes at each level do not have information regarding all of the packets in the multicast since an undefined number of packets will be generated in the future. Instead nodes at each level only have information regarding those message packets they have already received and no information regarding new message packets still being generated. Thus, when conventional forward error correction is applied to streaming media multicasts, check packets sent from one node may arrive too late to be useful for decoding missing message packets at another node.
Thus, there is a need in the art, for a forward error correction scheme that overcomes the above disadvantages.